package 二叉树的中序遍历;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution
{
    //递归法
    //借助栈的迭代方法
    //在树的深度优先遍历中（包括前序、中序、后序遍历），递归方法最为直观易懂，但考虑到效率，我们通常不推荐使用递归。
    //
    //栈迭代方法虽然提高了效率，但其嵌套循环却非常烧脑，不易理解，容易造成“一看就懂，一写就废”的窘况。
    // 而且对于不同的遍历顺序（前序、中序、后序），循环结构差异很大，更增加了记忆负担。
    //
    //因此，我在这里介绍一种“颜色标记法”（瞎起的名字……），兼具栈迭代方法的高效，又像递归方法一样简洁易懂，
    // 更重要的是，这种方法对于前序、中序、后序遍历，能够写出完全一致的代码。
    //
    //其核心思想如下：
    //
    //使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
    //如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
    //如果遇到的节点为灰色，则将节点的值输出。
    //
    class ColorNode
    {
        TreeNode node;
        String color;

        public ColorNode(TreeNode node, String color)
        {
            this.node = node;
            this.color = color;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root)
    {
        if (root == null) return new ArrayList<Integer>();

        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(root, "white"));

        while (!stack.empty())
        {
            ColorNode cn = stack.pop();

            if (cn.color.equals("white"))
            {
                if (cn.node.right != null)
                    stack.push(new ColorNode(cn.node.right, "white"));

                stack.push(new ColorNode(cn.node, "gray"));

                if (cn.node.left != null)
                    stack.push(new ColorNode(cn.node.left, "white"));
            }
            else
            {
                res.add(cn.node.val);
            }
        }

        return res;
    }

    public static void main(String[] args)
    {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        Solution solution = new Solution();
        List<Integer> res=solution.inorderTraversal(node1);
        for (int i = 0; i < res.size(); i++)
        {
            System.out.print(res.get(i)+",");
        }
    }
}
